{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Replace the Substring for Balanced String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: balancedString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #替换子串得到平衡字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个只含有&nbsp;<code>'Q', 'W', 'E',&nbsp;'R'</code>&nbsp;四种字符，且长度为 <code>n</code>&nbsp;的字符串。</p>\n",
    "\n",
    "<p>假如在该字符串中，这四个字符都恰好出现&nbsp;<code>n/4</code>&nbsp;次，那么它就是一个「平衡字符串」。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>给你一个这样的字符串 <code>s</code>，请通过「替换一个子串」的方式，使原字符串 <code>s</code> 变成一个「平衡字符串」。</p>\n",
    "\n",
    "<p>你可以用和「待替换子串」长度相同的&nbsp;<strong>任何</strong> 其他字符串来完成替换。</p>\n",
    "\n",
    "<p>请返回待替换子串的最小可能长度。</p>\n",
    "\n",
    "<p>如果原字符串自身就是一个平衡字符串，则返回 <code>0</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"QWER\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>s 已经是平衡的了。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"QQWE\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>我们需要把一个 'Q' 替换成 'R'，这样得到的 \"RQWE\" (或 \"QRWE\") 是平衡的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"QQQW\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们可以把前面的 \"QQ\" 替换成 \"ER\"。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"QQQQ\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>我们可以替换后 3 个 'Q'，使 s = \"QWER\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "\t<li><code>s.length</code>&nbsp;是&nbsp;<code>4</code>&nbsp;的倍数</li>\n",
    "\t<li><code>s</code>&nbsp;中只含有&nbsp;<code>'Q'</code>, <code>'W'</code>, <code>'E'</code>,&nbsp;<code>'R'</code>&nbsp;四种字符</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [replace-the-substring-for-balanced-string](https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [replace-the-substring-for-balanced-string](https://leetcode.cn/problems/replace-the-substring-for-balanced-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"QWER\"', '\"QQWE\"', '\"QQQW\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        n = len(s)\n",
    "        loc = {k: v - n // 4 for k, v in c.items() if v > n // 4}\n",
    "        if not loc: return 0\n",
    "        j = 0\n",
    "        ans = float('inf')\n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[i] in loc:\n",
    "                loc[s[i]] -= 1\n",
    "                \n",
    "            while max(loc.values()) <= 0:\n",
    "                ans = min(ans, i - j + 1)\n",
    "                if s[j] in loc:\n",
    "                    loc[s[j]] += 1\n",
    "                j += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        cnt = collections.Counter(s)\n",
    "        res = n = len(s)\n",
    "        left, avg = 0, n//4\n",
    "        if (all(avg >= cnt[x] for x in 'QWER')):\n",
    "            return 0\n",
    "        for right, c in enumerate(s):\n",
    "            cnt[c] -= 1\n",
    "            # 如果有窗口，那么最小窗口肯定包含在这个窗口里边，left指向的值加1后left右移，如果还是满足，再右移，直到不满足或比right大一个，当比right大一个时，right所指向的已经被left加1恢复了，此时就是原来的字符串，肯定不满足，right继续右移\n",
    "            while left < n and all(avg >= cnt[x] for x in 'QWER'):\n",
    "                res = min(res, right - left + 1)\n",
    "                cnt[s[left]] += 1\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        cnt = collections.Counter(s)\n",
    "        res = n = len(s)\n",
    "        left, avg = 0, n//4\n",
    "        if (all(avg >= cnt[x] for x in 'QWER')):\n",
    "            return 0\n",
    "        for right, c in enumerate(s):\n",
    "            cnt[c] -= 1\n",
    "            # 如果有窗口，那么最小窗口肯定包含在这个窗口里边，left指向的值加1后left右移，如果还是满足，再右移，直到不满足或比right大一个，当比right大一个时，right所指向的已经被left加1恢复了，此时就是原来的字符串，肯定不满足，right继续右移\n",
    "            while left < n and all(avg >= cnt[x] for x in 'QWER'):\n",
    "                res = min(res, right - left + 1)\n",
    "                cnt[s[left]] += 1\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        b = n // 4\n",
    "        from collections import Counter\n",
    "        counter = Counter(s)\n",
    "        counter = {key:value for key,value in counter.items() if value > b}\n",
    "        \n",
    "        if not counter or n < 4:\n",
    "            return 0\n",
    "        rmove = True\n",
    "        \n",
    "        l,r = 0,0\n",
    "        minlen = n\n",
    "        \n",
    "        while l <= r and r < n:\n",
    "            \n",
    "            if s[r] in counter and rmove:\n",
    "                counter[s[r]] -= 1\n",
    "            elif l > 0 and s[l - 1] in counter and not rmove:\n",
    "                counter[s[l - 1]] += 1\n",
    "\n",
    "            if {key:value for key,value in counter.items() if value > b}:\n",
    "                r += 1\n",
    "                rmove = True\n",
    "            else:\n",
    "                minlen = min(minlen, r - l + 1)\n",
    "                l += 1\n",
    "                rmove = False\n",
    "                         \n",
    "        return minlen\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        count_hash = {\"Q\":0,\"W\":0,\"E\":0,\"R\":0}\n",
    "        for ch in s:\n",
    "            count_hash[ch]+=1\n",
    "        \n",
    "        mark=0\n",
    "        n=len(s)\n",
    "        for key in count_hash:\n",
    "            if count_hash[key]!=n//4:\n",
    "                mark=1\n",
    "                break\n",
    "        if mark==0:\n",
    "            return 0\n",
    "\n",
    "        left,right=0,0\n",
    "        count_hash[s[right]]-=1\n",
    "        target=n//4\n",
    "        while right<n-1 and not (count_hash[\"Q\"]<=target and count_hash[\"W\"]<=target and \\\n",
    "            count_hash[\"E\"]<=target and count_hash[\"R\"]<=target):\n",
    "            right+=1\n",
    "            count_hash[s[right]]-=1\n",
    "        res=right-left+1\n",
    "        while right<n:\n",
    "            while left<=right and count_hash[\"Q\"]<=target and count_hash[\"W\"]<=target and \\\n",
    "                count_hash[\"E\"]<=target and count_hash[\"R\"]<=target:\n",
    "                count_hash[s[left]]+=1\n",
    "                left+=1\n",
    "            res=min(res,right-left+2)\n",
    "            if right>=n-1:\n",
    "                break\n",
    "            right+=1\n",
    "            count_hash[s[right]]-=1\n",
    "            while right<n-1 and not (count_hash[\"Q\"]<=target and count_hash[\"W\"]<=target and \\\n",
    "                count_hash[\"E\"]<=target and count_hash[\"R\"]<=target):\n",
    "                count_hash[s[left]]+=1\n",
    "                left+=1\n",
    "                right+=1\n",
    "                count_hash[s[right]]-=1\n",
    "            if not (count_hash[\"Q\"]<=target and count_hash[\"W\"]<=target and count_hash[\"E\"]<=target and \\\n",
    "                count_hash[\"R\"]<=target):\n",
    "                break\n",
    "\n",
    "        return res\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        m = collections.Counter(s)\n",
    "        if m['Q'] == m['E'] == m['W'] == m['R']:\n",
    "            return 0\n",
    "        m2 = collections.defaultdict(int)\n",
    "        for ch in m:\n",
    "            if m[ch] > len(s) // 4:\n",
    "                m2[ch] = m[ch] - len(s) // 4\n",
    "        l = 0\n",
    "        ans = float('inf')\n",
    "        m3 = collections.defaultdict(int)\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch in m2:\n",
    "                m3[ch] += 1\n",
    "            flag = 1\n",
    "            for ch in m2:\n",
    "                if m3[ch] < m2[ch]:\n",
    "                    flag = 0\n",
    "            if flag == 1:\n",
    "                while l < i and m3 != m2:\n",
    "                    if s[l] in m3:\n",
    "                        if m2[s[l]]==m3[s[l]]:\n",
    "                            break\n",
    "                        m3[s[l]] -= 1\n",
    "                    l += 1\n",
    "                while l < i and s[l] not in m3:\n",
    "                    l += 1\n",
    "                ans = min(ans, i - l + 1)\n",
    "                m3[s[l]] -= 1\n",
    "                l+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        # 统计每个字符的个数\n",
    "        s_c = dict(Counter(s))\n",
    "        # 统计哪些字符需要替换，以及需要被替换的个数\n",
    "        s_replaced = dict()\n",
    "        for ch, _c in s_c.items():\n",
    "            if _c > len(s) // 4:\n",
    "                s_replaced[ch] = _c - len(s) // 4\n",
    "        # 滑窗左边界\n",
    "        left = 0\n",
    "        # 滑窗右边界\n",
    "        right = 0\n",
    "        # 表示滑窗内包含的需要被替换的字符及其个数\n",
    "        origin_chs = {ch: 0 for ch in s_replaced.keys()}\n",
    "        rst = float('inf')\n",
    "        while right < len(s):\n",
    "            ch = s[right]\n",
    "            if ch not in origin_chs:\n",
    "                # 如果该字符不在需要替换的滑窗内，跳过，右边界前进，扩大窗口\n",
    "                right += 1\n",
    "                continue\n",
    "            # 找到一个需要替换的字符，相应个数+1\n",
    "            origin_chs[ch] += 1\n",
    "            if any([origin_chs[_ch] < s_replaced[_ch] for _ch in origin_chs.keys()]):\n",
    "                # 当需要被替换的字符有任何一个没有达到替换的个数时，右边界前进，扩大窗口\n",
    "                right += 1\n",
    "            else:\n",
    "                # 都达到个数后，开始处理\n",
    "                # 将前面预先加上的字符去掉\n",
    "                origin_chs[ch] -= 1\n",
    "                # 更新最小值\n",
    "                rst = min(rst, right - left + 1)\n",
    "                # 如果将要移出窗口的字符在需要替换的字符中，移出后，相应个数减一\n",
    "                if s[left] in origin_chs:\n",
    "                    origin_chs[s[left]] -= 1\n",
    "                # 左边界前进，缩小窗口\n",
    "                left += 1\n",
    "        return 0 if rst == float('inf') else rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        b = n // 4\n",
    "        from collections import Counter\n",
    "        counter = Counter(s)\n",
    "        counter = {key:value for key,value in counter.items() if value > b}\n",
    "        \n",
    "        if not counter or n < 4:\n",
    "            return 0\n",
    "        rmove = True\n",
    "        \n",
    "        l,r = 0,0\n",
    "        minlen = n\n",
    "        \n",
    "        while l <= r and r < n:\n",
    "            \n",
    "            if s[r] in counter and rmove:\n",
    "                counter[s[r]] -= 1\n",
    "            elif l > 0 and s[l - 1] in counter and not rmove:\n",
    "                counter[s[l - 1]] += 1\n",
    "\n",
    "            if {key:value for key,value in counter.items() if value > b}:\n",
    "                r += 1\n",
    "                rmove = True\n",
    "            else:\n",
    "                minlen = min(minlen, r - l + 1)\n",
    "                l += 1\n",
    "                rmove = False\n",
    "                         \n",
    "        return minlen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        balance = n // 4\n",
    "        count = collections.Counter(s)\n",
    "        sub_Q = count['Q'] - balance\n",
    "        sub_W = count['W'] - balance\n",
    "        sub_E = count['E'] - balance\n",
    "        sub_R = count['R'] - balance\n",
    "        if sub_Q == 0 and sub_W == 0 and sub_E == 0:\n",
    "            return 0\n",
    "        count_Q = 0\n",
    "        count_W = 0\n",
    "        count_E = 0\n",
    "        count_R = 0\n",
    "        start = 0\n",
    "        end = 0\n",
    "        ans = n\n",
    "        while end < n:\n",
    "            if s[end] == 'Q':\n",
    "                count_Q += 1\n",
    "            elif s[end] == 'W':\n",
    "                count_W += 1\n",
    "            elif s[end] == 'E':\n",
    "                count_E += 1\n",
    "            else:\n",
    "                count_R += 1\n",
    "            end += 1\n",
    "\n",
    "            while start < end:\n",
    "                sign = True\n",
    "                if count_Q < sub_Q:\n",
    "                    sign = False\n",
    "                if count_W < sub_W:\n",
    "                    sign = False\n",
    "                if count_E < sub_E:\n",
    "                    sign = False\n",
    "                if count_R < sub_R:\n",
    "                    sign = False\n",
    "\n",
    "                if sign:\n",
    "                    ans = min(ans, end - start)\n",
    "                    if s[start] == 'Q':\n",
    "                        count_Q -= 1\n",
    "                    elif s[start] == 'W':\n",
    "                        count_W -= 1\n",
    "                    elif s[start] == 'E':\n",
    "                        count_E -= 1\n",
    "                    else:\n",
    "                        count_R -= 1\n",
    "                    start += 1\n",
    "                else:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        slist=list(s)\n",
    "        n=len(slist)\n",
    "        ccnt=collections.Counter(slist)\n",
    "        chars=('Q','W','E','R')\n",
    "        base=n//4\n",
    "        neededcnt=dict()\n",
    "        ans=sys.maxsize\n",
    "\n",
    "        for k in ccnt:\n",
    "            if ccnt[k]>base:\n",
    "                neededcnt[k]=ccnt[k]-base\n",
    "\n",
    "        if not neededcnt:\n",
    "            return 0\n",
    "        chars = ('Q', 'W', 'E', 'R')\n",
    "        for c in chars:\n",
    "            neededcnt.setdefault(c,0)\n",
    "        \n",
    "        def included(need:dict,has:dict):\n",
    "            for c in chars:\n",
    "                need.setdefault(c,0)\n",
    "                has.setdefault(c,0)\n",
    "                n,h=need.get(c),has.get(c)\n",
    "                if h<n:\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        have={}\n",
    "        for c in chars:\n",
    "            have[c]=0\n",
    "\n",
    "        left=0\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            have[s[i]]+=1\n",
    "\n",
    "            while included(neededcnt,have):\n",
    "                length=i-left+1\n",
    "                ans=min(ans,length)\n",
    "                have[s[left]]-=1\n",
    "                left+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        count=collections.Counter(list(s))\n",
    "        #print(count)\n",
    "        for item in list(count.keys()):\n",
    "            if count[item]<=n//4:\n",
    "                del count[item]\n",
    "            else:\n",
    "                count[item]=count[item]-n//4\n",
    "        #print(count)\n",
    "        if not count:\n",
    "            return 0\n",
    "        left=0\n",
    "        right=1\n",
    "        res=float('inf')\n",
    "        while left<n and right<=n:\n",
    "            for k in count:\n",
    "                temp=s[left:right].count(k)\n",
    "                if temp<count[k]:\n",
    "                    right+=1\n",
    "                    break\n",
    "            else:\n",
    "                if right>=left:\n",
    "                    res=min(res,right-left)\n",
    "                left+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        def isValid(dic, taregt):\n",
    "            for k, v in dic.items():\n",
    "                if v > taregt:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        count = collections.Counter(s)\n",
    "        target = len(s) // 4\n",
    "        l, res = 0, len(s)\n",
    "        for r, c in enumerate(s):\n",
    "            if isValid(count, target):\n",
    "                return 0\n",
    "            count[c] -= 1\n",
    "            while l <= r and isValid(count, target):\n",
    "                res = min(res, r - l + 1)\n",
    "                count[s[l]] += 1\n",
    "                l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        cnt, m = Counter(s), len(s) // 4\n",
    "        if all(cnt[x] == m for x in \"QWER\"):\n",
    "            return 0\n",
    "                \n",
    "        ans, left = inf, 0 \n",
    "\n",
    "        for right, c in enumerate(s):\n",
    "            cnt[c] -= 1\n",
    "            while all(cnt[x] <= m for x in \"QWER\"):\n",
    "                ans = min(ans, right - left + 1)\n",
    "                cnt[s[left]] += 1\n",
    "                left += 1\n",
    "            \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        m = len(s)\n",
    "        n = m // 4\n",
    "        seen = dict()\n",
    "        seen['Q'] = 0\n",
    "        seen['W'] = 0\n",
    "        seen['E'] = 0\n",
    "        seen['R'] = 0\n",
    "        for ch in s:\n",
    "            seen[ch] += 1\n",
    "        if min(seen.values()) == max(seen.values()):\n",
    "            return 0\n",
    "        left = 0\n",
    "        ans = m + 1\n",
    "        for right, ch in enumerate(s):\n",
    "            seen[ch] -= 1\n",
    "            while left <= right and max(seen.values()) <= n:\n",
    "                if max(seen.values()) == n:\n",
    "                    ans = min(ans, right - left + 1)\n",
    "                seen[s[left]] += 1\n",
    "                left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def balancedString(self, s: str) -> int:\r\n",
    "        cnt = Counter(s)\r\n",
    "        m = len(s) // 4\r\n",
    "        ans = inf\r\n",
    "        left = 0\r\n",
    "        if all(cnt[x] == m for x in \"QWER\"):\r\n",
    "            return 0\r\n",
    "        \r\n",
    "        for right, x in enumerate(s):\r\n",
    "            cnt[x] -= 1\r\n",
    "            while all(cnt[x] <= m for x in \"QWER\"):\r\n",
    "                ans = min(ans, right - left + 1)\r\n",
    "                cnt[s[left]] += 1\r\n",
    "                left += 1\r\n",
    "        return ans\r\n",
    "        \r\n",
    "\r\n",
    "\r\n",
    "        \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        s_cnt = cnt = Counter()\n",
    "        n = int(len(s) / 4)\n",
    "        for i in s:\n",
    "            s_cnt[i] += 1\n",
    "\n",
    "        if all(map(lambda x: x == n, list(s_cnt.values()))):\n",
    "            return 0\n",
    "        if s is None:\n",
    "            return 0\n",
    "        left = 0\n",
    "        ans = len(s) + 1\n",
    "        for right, x in enumerate(s):\n",
    "            # print(right)\n",
    "            s_cnt[x] -= 1\n",
    "            \n",
    "            # print(s_cnt)\n",
    "            \n",
    "            while all(map(lambda x: x <= n, list(s_cnt.values()))):\n",
    "                # print(s_cnt)\n",
    "                print(right,left)\n",
    "                ans = min(ans, right - left + 1)\n",
    "                print(ans)\n",
    "                s_cnt[s[left]] += 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        nums = {key: 0 for key in 'QWER'}\n",
    "        m = n / 4\n",
    "        res = []\n",
    "\n",
    "        while left < n:\n",
    "            ch = s[left]\n",
    "            nums[ch] += 1\n",
    "            if nums[ch] > m:\n",
    "                nums[ch] -= 1\n",
    "                left -= 1\n",
    "                break\n",
    "            else:\n",
    "                left += 1\n",
    "\n",
    "        if left == n:\n",
    "            return 0\n",
    "\n",
    "        while right >= left:\n",
    "            ch = s[right]\n",
    "            nums[ch] += 1\n",
    "            if nums[ch] > m:\n",
    "                res.append(right - left)\n",
    "                while left >= 0:\n",
    "                    ch2 = s[left]\n",
    "                    nums[ch2] -= 1\n",
    "                    left -= 1\n",
    "                    if ch2 == ch:\n",
    "                        break\n",
    "                if left < 0 and nums[ch] > m:\n",
    "                    break\n",
    "            right -= 1\n",
    "        \n",
    "        # print(s, m)\n",
    "        # print(nums)\n",
    "        # print(left,right)\n",
    "        return min(res)\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        l, n = 0, len(s) // 4\n",
    "        ans = inf\n",
    "        S = Counter(s)\n",
    "        if all(S[x] == n for x in \"QWER\"):\n",
    "            return 0\n",
    "        for r, x in enumerate(s):\n",
    "            S[x] -= 1\n",
    "            while all(S[c] <= n for c in \"QWER\"):\n",
    "                ans = min(ans, r - l + 1)\n",
    "                S[s[l]] += 1\n",
    "                l += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        if length % 4 != 0:\n",
    "            return -1\n",
    "        countMap = {}\n",
    "        for i in range(length):\n",
    "            if s[i] in countMap:\n",
    "                countMap[s[i]] += 1\n",
    "            else:\n",
    "                countMap[s[i]] = 1\n",
    "        minSub = 0\n",
    "        for k in countMap:\n",
    "            if countMap[k] > length / 4:\n",
    "                minSub += countMap[k] - length / 4\n",
    "\n",
    "        if minSub == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            left = 0\n",
    "            right = 0\n",
    "            res = length\n",
    "            while right < length:\n",
    "                countMap[s[right]] -= 1\n",
    "                c = self.check(countMap, length / 4)\n",
    "                if c:\n",
    "                    res = min(res, right - left + 1)\n",
    "                    while left <= right:\n",
    "                        countMap[s[left]] += 1\n",
    "                        if self.check(countMap, length / 4):\n",
    "                            res = min(res, right - left)\n",
    "                            left += 1\n",
    "                        else:\n",
    "                            left += 1\n",
    "                            break\n",
    "                right += 1\n",
    "            return res\n",
    "    def check(self, countMap, n):\n",
    "        res = True\n",
    "        for k in countMap:\n",
    "            if countMap[k] > n:\n",
    "                res = False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        if length % 4 != 0:\n",
    "            return -1\n",
    "        countMap = {}\n",
    "        for i in range(length):\n",
    "            if s[i] in countMap:\n",
    "                countMap[s[i]] += 1\n",
    "            else:\n",
    "                countMap[s[i]] = 1\n",
    "        minSub = 0\n",
    "        for k in countMap:\n",
    "            if countMap[k] > length / 4:\n",
    "                minSub += countMap[k] - length / 4\n",
    "\n",
    "        if minSub == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            left = 0\n",
    "            right = 0\n",
    "            res = length\n",
    "            while right < length:\n",
    "                countMap[s[right]] -= 1\n",
    "                c = self.check(countMap, length / 4)\n",
    "                if c:\n",
    "                    res = min(res, right - left + 1)\n",
    "                    while left <= right:\n",
    "                        countMap[s[left]] += 1\n",
    "                        if self.check(countMap, length / 4):\n",
    "                            res = min(res, right - left)\n",
    "                            left += 1\n",
    "                        else:\n",
    "                            left += 1\n",
    "                            break\n",
    "                right += 1\n",
    "            return res\n",
    "    def check(self, countMap, n):\n",
    "        res = True\n",
    "        for k in countMap:\n",
    "            if countMap[k] > n:\n",
    "                res = False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # 挑出s中出现次数大于n//4的字符，将其频率减去n//4存入哈希表h_target中\n",
    "        h_target = {k: v-n//4 for k,v in Counter(s).items() if v > n//4}\n",
    "        \n",
    "        # 如果哈希表长度为0，说明所有字符出现次数均为n//4，原字符串即为平衡字符串，直接返回0\n",
    "        if len(h_target) == 0:\n",
    "            return 0\n",
    "        # 否则，需要使用滑动窗口算法，找到包含所有h_target的最短字符串，\n",
    "        # 用一个哈希表h_window储存滑动窗口中所需要的字符的频率\n",
    "        h_window = {k: 0 for k in h_target}\n",
    "        left, ans = 0, inf\n",
    "        # 以下分析使用滑动窗口三问三答：\n",
    "        for right, ch in enumerate(s):\n",
    "            if ch in h_target:      # Q1：right对应的ch如何操作？\n",
    "                h_window[ch] += 1   # A1：如果ch是h_target中的键，则在h_windows中进行计数\n",
    "            # Q2：何时需要left右移？何时left停止右移？\n",
    "            # A2：h_window中对应字符的频率均大于等于h_target，left右移\n",
    "            if (all(h_window[k] >= h_target[k] for k in h_target)):\n",
    "                while(all(h_window[k] >= h_target[k] for k in h_target)):\n",
    "                    if s[left] in h_target:\n",
    "                        h_window[s[left]] -= 1\n",
    "                    left += 1\n",
    "                # Q3：何时进行ans的更新？\n",
    "                # A3：左移结束，此时s[left-1:right+1]为符合要求的字符串\n",
    "                # 其长度为right-left+2\n",
    "                ans = min(ans, right-left+2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balancedString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnts = [0] * 4\n",
    "        arr = [0] * n\n",
    "        for i in range(n):\n",
    "            match s[i]:\n",
    "                case 'Q':\n",
    "                    cnts[0] += 1\n",
    "                    arr[i] = 0\n",
    "\n",
    "                case 'W':\n",
    "                    cnts[1] += 1\n",
    "                    arr[i] = 1\n",
    "\n",
    "                case 'E':\n",
    "                    cnts[2] += 1\n",
    "                    arr[i] = 2\n",
    "\n",
    "                case 'R':\n",
    "                    cnts[3] += 1\n",
    "                    arr[i] = 3\n",
    "        ans = n\n",
    "        target = n // 4\n",
    "        l,r = 0,0\n",
    "        if self.ok(cnts, 0, target):\n",
    "            return 0\n",
    "        for r in range(n):\n",
    "            cnts[arr[r]] -= 1\n",
    "            while self.ok(cnts, r-l+1, target):\n",
    "                ans = min(ans, r-l+1)\n",
    "                cnts[arr[l]] += 1\n",
    "                l += 1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    def ok(self, cnts: List[int], leng: int, target: int) -> bool:\n",
    "        for i in range(4):\n",
    "            if cnts[i] > target:\n",
    "                return False\n",
    "            leng -= target - cnts[i]\n",
    "        return leng == 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
